﻿using System;
using System.Collections.Generic;
using System.Text;

namespace MyZip
{
    class Compression
    {
        public Byte[] Input;
        public int InputLength;
        public Byte[] Output;
        public int OutputLength;

        public void CompressionFunc()
        {
            int pInput = 0;
            int pOutput = 0;
            int ppOutput = 0;
            Output = new Byte[Input.Length * 3 / 2];
            Array.Clear(Output, 0, Output.Length);

            Byte[] Pre = new Byte[InputLength];

            for (int i = 0; i < InputLength; ++i)
                Pre[i] = (Byte)(Input[i] / (1 << (Consts.DifBits - 1)));

            while (pInput < InputLength)
            {
                int DicStart = (pInput > Consts.DicLength) ? pInput - Consts.DicLength : 0;
                int BufferEnd = (pInput + Consts.BufferLength > InputLength) ? InputLength - 1 : pInput + Consts.BufferLength - 1;
                bool MatchFound = false;

                //first, accurate matching
                int[] Next = GetNext(Input, pInput, BufferEnd);

                for (int i = BufferEnd; i >= pInput + 1; --i)//the length of accurate matched string must be bigger than 3
                {
                    int result = KMPStrMatching(Input, DicStart, i - 1, pInput, i, Next);

                    if (result != -1)
                    {
                        MatchFound = true;
                        Byte Id = 0;
                        int StartPoint = pInput - DicStart - result;
                        Byte Len = (Byte)(i - pInput + 1);
                        InsertBits(Output, ref pOutput, ref ppOutput, Id, 2);
                        InsertBits(Output, ref pOutput, ref ppOutput, StartPoint, Consts.DicBits);
                        InsertBits(Output, ref pOutput, ref ppOutput, Len, Consts.BufferBits);
                        pInput = i + 1;
                        break;
                    }
                }

                Next = null;

                if (MatchFound)
                    continue;

                //second, inaccurate matching
                Next = GetNext(Pre, pInput, BufferEnd);

                for (int i = BufferEnd; i >= pInput + (Consts.DicBits + Consts.BufferBits) / (8 - Consts.DifBits); --i)
                {
                    int result = KMPStrMatching(Pre, DicStart, i - 1, pInput, i, Next);

                    if (result != -1)
                    {
                        MatchFound = true;
                        Byte Id = 3;
                        int StartPoint = pInput - DicStart - result;
                        Byte Len = (Byte)(i - pInput + 1);
                        InsertBits(Output, ref pOutput, ref ppOutput, Id, 2);
                        InsertBits(Output, ref pOutput, ref ppOutput, StartPoint, Consts.DicBits);
                        InsertBits(Output, ref pOutput, ref ppOutput, Len, Consts.BufferBits);

                        //Insert Information Of Difference
                        for (int j = DicStart + result, k = pInput; j < DicStart + result + i - pInput + 1; j++, k++)
                        {
                            int dif = Input[k] - Input[j] + (1 << (Consts.DifBits - 1));
                            InsertBits(Output, ref pOutput, ref ppOutput, (Byte)dif, Consts.DifBits);
                        }
                        pInput = i + 1;
                        break;
                    }
                }

                Next = null;

                if (MatchFound)
                    continue;

                //Third, just copy the byte to the output file
                InsertBits(Output, ref pOutput, ref ppOutput, (Byte)2, 2);
                InsertBits(Output, ref pOutput, ref ppOutput, Input[pInput], 8);
                pInput++;
            }

            //finally, add a symbol of the end of file
            InsertBits(Output, ref pOutput, ref ppOutput, (Byte)1, 2);
            if (ppOutput != 0)
                InsertBits(Output, ref pOutput, ref ppOutput, (Byte)0, 8 - ppOutput);

            OutputLength = pOutput;
        }

        int[] GetNext(Byte[] s, int start, int end)
        {
            int[] Next = new int[end - start + 1];
            int i = 0;
            int k = -1;
            int m = start - end + 1;

            Next[0] = -1;
            while (i < m)
            {
                while (k >= 0 && s[i + start] != s[k + start])
                    k = Next[k];
                i++;
                k++;
                if (i == m)
                    break;
                if (s[i + start] == s[k + start])
                    Next[i] = Next[k];
                else
                    Next[i] = k;
            }

            return Next;
        }

        int KMPStrMatching(Byte[] s, int Tstart, int Tend, int Pstart, int Pend, int[] Next)
        {
            int i = 0, j = 0;
            int Tlen = Tend - Tstart + 1, Plen = Pend - Pstart + 1;

            if (Tlen <= 0 || Plen <= 0 || Plen > Tlen)
                return -1;

            while (i < Plen && j < Tlen)
                if (i == -1 || s[Tstart + j] == s[Pstart + i])
                {
                    i++;
                    j++;
                }
                else
                    i = Next[i];

            if (i >= Plen)
                return (j - Plen);
            else
                return -1;
        }

        //Native Algorithm
        int InaccurateMatching(Byte[] s, int Tstart, int Tend, int Pstart, int Pend)
        {
            int i = 0, j = 0;
            int Plen = Pend - Pstart + 1;
            int Tlen = Tend - Tstart + 1;

            if (Tlen <= 0 || Plen <= 0 || Plen > Tlen)
                return -1;

            while(i < Plen && j < Tlen)
            {
                if ((s[j + Tstart] - s[i + Pstart]) <= (1 << (Consts.DifBits - 1)) && (s[i + Pstart] - s[j + Tstart]) <= (1 << (Consts.DifBits - 1) - 1))
                {
                    i++;
                    j++;
                }
                else
                {
                    j = j - i + 1;
                    i = 0;
                }
            }

            if (i >= Plen)
                return j - Plen + 1;
            else
                return -1;
        }

        void InsertBits(Byte[] Dest, ref int p, ref int pp, int bits, int len)
        {
            if (len <= 8)
                InsertBits(Dest, ref p, ref pp, (Byte)bits, len);
            else
            {
                Byte temp = (Byte)(bits & 0xff);
                bits = bits >> 8;
                len -= 8;
                InsertBits(Dest, ref p, ref pp, bits, len);
                InsertBits(Dest, ref p, ref pp, temp, 8);
            }
        }
                        
        void InsertBits(Byte[] Dest, ref int p, ref int pp, Byte bits, int len)
        {
            if (pp + len - 1 <= 7)
            {
                int temp = Dest[p];
                temp = temp | (bits << (8 - pp - len));
                Dest[p] = (Byte)temp;
                if (pp + len == 8)
                    p++;
                pp = (pp + len) % 8;
            }
            else
            {
                int len1 = 8 - pp;
                int len2 = len - len1;
                int bits1;
                int bits2;

                bits2 = ((1 << len2) - 1) & bits;
                bits1 = ((1 << len1) - 1) & (bits >> len2);

                int temp = Dest[p];
                temp = temp | bits1;
                Dest[p] = (Byte)temp;
                p++; pp = 0;

                Dest[p] = (Byte)(bits2 << (8 - pp - len2));
                pp = len2;
            }
        }
    }
}
